#define _CRT_SECURE_NO_WARNINGS
//class Solution {
//public:
//    struct Com
//    {
//        bool operator()(ListNode* l, ListNode* r)
//        {
//            return l->val < r->val;
//        }
//    };
//    ListNode* sortList(ListNode* head) {
//        vector<ListNode*> v;
//        ListNode* cur = head;
//        while (cur)
//        {
//            v.push_back(cur);
//            cur = cur->next;
//        }
//        sort(v.begin(), v.end(), Com());
//        ListNode* _head = nullptr, * _tail = nullptr;
//        for (auto e : v)
//        {
//            if (_head == nullptr)
//            {
//                _head = _tail = e;
//            }
//            else
//            {
//                _tail->next = e;
//                _tail = _tail->next;
//            }
//        }
//        if (_tail)
//            _tail->next = nullptr;
//        return _head;
//    }
//};
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    TreeNode* dfs(vector<int>& nums, int left, int right)
//    {
//        if (left > right)
//            return nullptr;
//        int mid = (left + right) / 2;
//        TreeNode* root = new TreeNode(nums[mid]);
//        root->left = dfs(nums, left, mid - 1);
//        root->right = dfs(nums, mid + 1, right);
//        return root;
//    }
//    TreeNode* sortedArrayToBST(vector<int>& nums) {
//        return dfs(nums, 0, nums.size() - 1);
//    }
//};
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    int ret = 0x3f3f3f3f;
//    vector<int> v;
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr)
//            return;
//        dfs(root->left);
//        v.push_back(root->val);
//        dfs(root->right);
//    }
//    int getMinimumDifference(TreeNode* root) {
//        dfs(root);
//        for (int i = 1; i < v.size(); i++)
//            ret = min(ret, v[i] - v[i - 1]);
//        return ret;
//        // if(root==nullptr)
//        //     return 0;
//        // if(root->left)
//        // {
//        //     ret = min(ret,root->val-root->left->val);
//        // }
//        // if(root->right)
//        // {
//        //     ret = min(ret,root->right->val-root->val);
//        // }
//        // getMinimumDifference(root->left);
//        // getMinimumDifference(root->right);
//        // return ret;
//    }
//};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    vector<double> averageOfLevels(TreeNode* root) {
//        queue<TreeNode*> q;
//        if (root)
//            q.push(root);
//        vector<double> v;
//        while (!q.empty())
//        {
//            int size = q.size();
//            long long sum = 0;
//            for (int i = 0; i < size; i++)
//            {
//                TreeNode* tmp = q.front();
//                q.pop();
//                sum += tmp->val;
//                if (tmp->left)
//                    q.push(tmp->left);
//                if (tmp->right)
//                    q.push(tmp->right);
//            }
//            v.push_back((double)sum / size);
//        }
//        return v;
//    }
//};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    vector<int> rightSideView(TreeNode* root) {
//        queue<TreeNode*> q;
//        if (root)
//            q.push(root);
//        vector<int> ret;
//        while (!q.empty())
//        {
//            int size = q.size();
//            for (int i = 0; i < size; i++)
//            {
//                TreeNode* tmp = q.front();
//                q.pop();
//                if (tmp->left)
//                    q.push(tmp->left);
//                if (tmp->right)
//                    q.push(tmp->right);
//                if (i == size - 1)
//                {
//                    ret.push_back(tmp->val);
//                }
//            }
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int count = 0;
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr)
//            return;
//        count++;
//        dfs(root->left);
//        dfs(root->right);
//    }
//    int countNodes(TreeNode* root) {
//        dfs(root);
//        return count;
//    }
//};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class BSTIterator {
//public:
//    BSTIterator(TreeNode* root) {
//        _root = root;
//        cur = root;
//        // while(cur&&cur->left)
//        // {
//        //     st.push(cur);
//        //     cur = cur->left;
//        // }
//    }
//
//    int next() {
//        while (cur != nullptr)
//        {
//            st.push(cur);
//            cur = cur->left;
//        }
//        cur = st.top();
//        st.pop();
//        int ret = cur->val;
//        cur = cur->right;
//        return ret;
//        // TreeNode* ret = cur;
//        // if(!st.empty())
//        // {
//        //     cur = st.top();
//        //     st.pop();
//        // }
//        // else
//        // {
//        //     cur = nullptr;
//        // }
//        // if(cur&&cur->right)
//        // {
//        //     TreeNode* cur1 = cur->right; 
//        //     while(cur1->left)
//        //     {
//        //         st.push(cur1);
//        //         cur1 = cur1->left;
//        //     }
//        // }
//        // return  ret->val;
//    }
//
//    bool hasNext() {
//        return cur != nullptr || !st.empty();
//        //return cur!=nullptr;
//        // TreeNode* ret = cur;
//        // if(!st.empty())
//        // {
//        //     cur = st.top();
//        //     st.pop();
//        // }
//        // if(cur->right)
//        // {
//        //     TreeNode* cur1 = cur->right; 
//        //     while(cur1->left)
//        //     {
//        //         st.push(cur1);
//        //         cur1 = cur1->left;
//        //     }
//        // }
//    }
//    TreeNode* _root;
//    stack<TreeNode*> st;
//    TreeNode* cur;
//};
//
///**
// * Your BSTIterator object will be instantiated and called as such:
// * BSTIterator* obj = new BSTIterator(root);
// * int param_1 = obj->next();
// * bool param_2 = obj->hasNext();
// */